{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Number of Arrows to Burst Balloons"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findMinArrowShots"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #用最少数量的箭引爆气球"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组&nbsp;<code>points</code>&nbsp;，其中<code>points[i] = [x<sub>start</sub>, x<sub>end</sub>]</code>&nbsp;表示水平直径在&nbsp;<code>x<sub>start</sub></code>&nbsp;和&nbsp;<code>x<sub>end</sub></code>之间的气球。你不知道气球的确切 y 坐标。</p>\n",
    "\n",
    "<p>一支弓箭可以沿着 x 轴从不同点 <strong>完全垂直</strong> 地射出。在坐标 <code>x</code> 处射出一支箭，若有一个气球的直径的开始和结束坐标为 <code>x</code><sub><code>start</code>，</sub><code>x</code><sub><code>end</code>，</sub> 且满足 &nbsp;<code>x<sub>start</sub>&nbsp;≤ x ≤ x</code><sub><code>end</code>，</sub>则该气球会被 <strong>引爆</strong>&nbsp;<sub>。</sub>可以射出的弓箭的数量 <strong>没有限制</strong> 。 弓箭一旦被射出之后，可以无限地前进。</p>\n",
    "\n",
    "<p>给你一个数组 <code>points</code> ，<em>返回引爆所有气球所必须射出的 <strong>最小</strong> 弓箭数&nbsp;</em>。</p>\n",
    "&nbsp;\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>points = [[10,16],[2,8],[1,6],[7,12]]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>气球可以用2支箭来爆破:\n",
    "-在x = 6处射出箭，击破气球[2,8]和[1,6]。\n",
    "-在x = 11处发射箭，击破气球[10,16]和[7,12]。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>points = [[1,2],[3,4],[5,6],[7,8]]\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>每个气球需要射出一支箭，总共需要4支箭。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>points = [[1,2],[2,3],[3,4],[4,5]]\n",
    "<strong>输出：</strong>2\n",
    "解释：气球可以用2支箭来爆破:\n",
    "- 在x = 2处发射箭，击破气球[1,2]和[2,3]。\n",
    "- 在x = 4处射出箭，击破气球[3,4]和[4,5]。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" /></p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= points.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>points[i].length == 2</code></li>\n",
    "\t<li><code>-2<sup>31</sup>&nbsp;&lt;= x<sub>start</sub>&nbsp;&lt; x<sub>end</sub>&nbsp;&lt;= 2<sup>31</sup>&nbsp;- 1</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-number-of-arrows-to-burst-balloons](https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-number-of-arrows-to-burst-balloons](https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[10,16],[2,8],[1,6],[7,12]]', '[[1,2],[3,4],[5,6],[7,8]]', '[[1,2],[2,3],[3,4],[4,5]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinArrowShots(self, points: List[List[int]]) -> int:\n",
    "        if not points:\n",
    "            return 0\n",
    "        points.sort(key = lambda x: x[1])\n",
    "        arrows = 1\n",
    "        first_end = points[0][1]\n",
    "        for x_start, x_end in points:\n",
    "            if first_end < x_start:\n",
    "                arrows += 1\n",
    "                first_end = x_end\n",
    "        return arrows"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinArrowShots(self, points: 'List[List[int]]') -> 'int':\n",
    "        \n",
    "        \n",
    "        if not points:\n",
    "            return 0\n",
    "        points.sort() # 按照起始点排序\n",
    "        begin_index = points[0][0]\n",
    "        end_index = points[0][1]\n",
    "        jian = 1\n",
    "        for i in range(1,len(points)):\n",
    "            if points[i][0] <= end_index:\n",
    "                begin_index = points[i][0] #更新起始点\n",
    "                if points[i][1] < end_index:\n",
    "                    end_index = points[i][1] #更新结束点\n",
    "            else:\n",
    "                jian +=1\n",
    "                begin_index = points[i][0]\n",
    "                end_index = points[i][1]\n",
    "        return jian"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinArrowShots(self, points: List[List[int]]) -> int:\n",
    "        length = len(points)\n",
    "        if length == 0:\n",
    "            return 0\n",
    "        elif length == 1:\n",
    "            return 1\n",
    "        points.sort(key = lambda x:x[0])\n",
    "        res = 1\n",
    "        end = points[0][1]\n",
    "        for p in points[1:]:\n",
    "            if p[0] > end:\n",
    "                res += 1\n",
    "                end = p[1]\n",
    "            else:\n",
    "                end = min(end, p[1])\n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinArrowShots(self, points):\n",
    "        \"\"\"\n",
    "        :type points: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not points:\n",
    "            return 0\n",
    "        points = sorted(points,key=lambda s:s[1])\n",
    "        # print(points)\n",
    "        temp = 0\n",
    "        count = 0\n",
    "        for i in range(len(points)-1):\n",
    "            if points[temp][1] >= points[i+1][0]:\n",
    "                count += 1\n",
    "                #print(count)\n",
    "            else:\n",
    "                temp = i+1\n",
    "        return len(points)-count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinArrowShots(self, points):\n",
    "        \"\"\"\n",
    "        :type points: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if len(points)==0:\n",
    "            return 0\n",
    "        points = sorted(points)\n",
    "       \n",
    "        shoot_begin = points[0][0]\n",
    "        shoot_end = points[0][1]\n",
    "        shoot_num = 1\n",
    "        for i in range(len(points)):\n",
    "            if i == 0:\n",
    "                continue\n",
    "            if points[i][0] < shoot_end or points[i][0] == shoot_end:\n",
    "                shoot_begin = points[i][0]\n",
    "                if shoot_end > points[i][1]:\n",
    "                    shoot_end = points[i][1]\n",
    "            else:\n",
    "                shoot_num = shoot_num + 1\n",
    "                shoot_begin = points[i][0]\n",
    "                shoot_end = points[i][1]\n",
    "        return shoot_num\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinArrowShots(self, points):\n",
    "        \"\"\"\n",
    "        :type points: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if len(points) <= 0:\n",
    "            return 0\n",
    "        points = sorted(points, key=lambda x: x[1])\n",
    "        end = points[0][1]\n",
    "        cnt = 1\n",
    "        for i in range(1, len(points)):\n",
    "            if points[i][0] <= end:\n",
    "                continue\n",
    "            cnt += 1\n",
    "            end = points[i][1]\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinArrowShots(self, points: List[List[int]]) -> int:\n",
    "        points.sort(key = lambda x: x[1])\n",
    "        arr = 0\n",
    "        while(points):\n",
    "            shot = points[0][1]\n",
    "            arr += 1\n",
    "            while points and points[0][0] <= shot:\n",
    "                points.pop(0)  # can be changed\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinArrowShots(self, points: List[List[int]]) -> int:\n",
    "        if len(points)<=1:\n",
    "            return len(points)\n",
    "        points.sort(reverse=False)\n",
    "        i=1\n",
    "        while i<len(points):\n",
    "            (al,ar),(bl,br)=points[i-1],points[i]\n",
    "            if bl<=ar:\n",
    "                points[i-1]=bl,min(ar,br)\n",
    "                points.pop(i)\n",
    "            else:\n",
    "                i=i+1\n",
    "        return len(points)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinArrowShots(self, points: List[List[int]]) -> int:\n",
    "        points.sort(key=lambda x:x[1])\n",
    "        res=1\n",
    "        x=points.pop()\n",
    "        while len(points)>0:\n",
    "            y=points.pop()\n",
    "            if x[0]>y[1]:\n",
    "                x=y\n",
    "                res+=1\n",
    "            elif x[0]<=y[1] and x[0]>y[0]:\n",
    "                x[1]=y[0]\n",
    "            elif x[0]<y[0]:\n",
    "                x[0]=y[0]\n",
    "                x[1]=y[1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinArrowShots(self, points: List[List[int]]) -> int:\n",
    "        heapq.heapify(points)\n",
    "        ret = 1\n",
    "        cur = heapq.heappop(points)\n",
    "        while len(points):\n",
    "            nxt = heapq.heappop(points)\n",
    "            if nxt[0] > cur[1]:\n",
    "                ret += 1\n",
    "                cur = nxt\n",
    "            else:\n",
    "                cur[1] = min(cur[1], nxt[1])\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinArrowShots(self, points: List[List[int]]) -> int:\n",
    "        points.sort(reverse=False)\n",
    "        area = points[0]\n",
    "        count = 1\n",
    "        for point in points:\n",
    "            if point[0] <= area[1]:\n",
    "                area[0] = max(area[0], point[0])\n",
    "                area[1] = min(area[1], point[1])\n",
    "            else:\n",
    "                count +=1\n",
    "                area = point\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinArrowShots(self, points: List[List[int]]) -> int:\n",
    "        points.sort(key=lambda x:x[1])\n",
    "        count=1\n",
    "        right=points[0][1]\n",
    "        for i in points[1:]:\n",
    "            if i[0]>right:\n",
    "                right=i[1]\n",
    "                count+=1     \n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinArrowShots(self, points: List[List[int]]) -> int:\n",
    "        points.sort(key=lambda x:x[1])\n",
    "        print(points)\n",
    "        cnt=1\n",
    "        now=points[0][1]\n",
    "        for i in range(1,len(points)):\n",
    "            if(points[i][0]<=now):\n",
    "                continue\n",
    "            \n",
    "            cnt+=1\n",
    "            now=points[i][1]\n",
    "        return cnt\n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinArrowShots(self, points: List[List[int]]) -> int:\n",
    "        if not points:\n",
    "            return 0\n",
    "        l = len(points)\n",
    "        if l ==1:\n",
    "            return 1\n",
    "        points.sort()\n",
    "        print(points)\n",
    "        ans = set()\n",
    "        left, right = points[0][0], points[0][1]\n",
    "        print(left)\n",
    "        print(right)\n",
    "        for cur_l, cur_r in points:\n",
    "            if cur_l > right:\n",
    "                ans.add((left, right))\n",
    "                left = cur_l\n",
    "                right = cur_r\n",
    "            else:\n",
    "                left = max(left, cur_l)\n",
    "                right = min(right, cur_r)\n",
    "        ans.add((left, right))\n",
    "        print(ans)\n",
    "        return len(ans)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinArrowShots(self, points: List[List[int]]) -> int:\n",
    "        # 对start, end打混一块排序\n",
    "        total = []\n",
    "        for pair_index in range(len(points)):\n",
    "            pair = points[pair_index]\n",
    "            start, end = pair[0], pair[1]\n",
    "            total.append([start, 0, pair_index])\n",
    "            total.append([end, 1, pair_index])\n",
    "        total.sort(key = lambda x : (x[0], x[1]))\n",
    "\n",
    "        ans = 0\n",
    "        \n",
    "        left = 0\n",
    "        skip = 0\n",
    "        seen = set()\n",
    "        for point in total:\n",
    "            _, is_right, index = point\n",
    "            if not is_right:\n",
    "                seen.add(index)\n",
    "            else:\n",
    "                if index in seen:\n",
    "                    ans += 1\n",
    "                    seen = set()\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinArrowShots(self, points: List[List[int]]) -> int:\n",
    "        \"\"\"排序+栈\"\"\"\n",
    "        que = list()  # 存区间端点和下标\n",
    "        for idx, (start, end) in enumerate(points):\n",
    "            que.append((start, idx+1)) \n",
    "            que.append((end, -idx-1))\n",
    "        que.sort(key=lambda x: (x[0], -x[1]))\n",
    "\n",
    "        ans = 0\n",
    "        visit = set()\n",
    "        stack = list()\n",
    "        for val, idx in que:\n",
    "            if idx > 0:  # 左端点\n",
    "                stack.append(idx)\n",
    "            else:\n",
    "                if -idx not in visit:\n",
    "                    ans += 1\n",
    "                    while stack:\n",
    "                        visit.add(stack.pop(0))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinArrowShots(self, points: List[List[int]]) -> int:\n",
    "        self.quickSort(points,0,len(points)-1)\n",
    "        res = 0\n",
    "        end = -20000000000\n",
    "        for i in range(0,len(points)):\n",
    "            if points[i][0] > end :\n",
    "                res +=1\n",
    "                end = points[i][1]\n",
    "        return res\n",
    "    def quickSort(self,shulie,l,r):\n",
    "        i = l\n",
    "        j = r\n",
    "        if i > j:\n",
    "            return\n",
    "        zhou = shulie[i]\n",
    "        while i < j:\n",
    "            while i < j and shulie[j][1] >= zhou[1]:\n",
    "                j -=1\n",
    "            shulie[i] = shulie[j]\n",
    "            while i < j and shulie[i][1] <= zhou[1]:\n",
    "                i +=1\n",
    "            shulie[j] = shulie[i]\n",
    "        shulie[i] = zhou\n",
    "        self.quickSort(shulie,l,i-1)\n",
    "        self.quickSort(shulie,i+1,r)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "先排序再贪心，这样就少了每次递归的时候都要排序了。\n",
    "直接贪心的源代码在下面注释着，跪在37/44了，超出时间限制\n",
    "'''\n",
    "class Solution:\n",
    "    def takeSecend(self,elem):\n",
    "        return elem[1]\n",
    "    def findMinArrowShots(self, points: List[List[int]]) -> int:\n",
    "        points.sort(key=self.takeSecend)\n",
    "        return self.Shots(points) \n",
    "    def Shots(self,points:List[List[int]]) -> int:\n",
    "        if len(points) in (0,1): return len(points)\n",
    "        else:\n",
    "            minleft = points[0]\n",
    "            for i in points[:]:\n",
    "                if minleft[1] >= i[0]:\n",
    "                    points.remove(i)\n",
    "            return self.Shots(points) + 1\n",
    "'''\n",
    "直接贪心\n",
    "class Solution:\n",
    "    def findMinArrowShots(self, points: List[List[int]]) -> int:\n",
    "        if len(points) in (0,1): return len(points)\n",
    "        else:\n",
    "            minleft = points[0]\n",
    "            for i in range(1,len(points)):\n",
    "                if minleft[1] > points[i][1]:minleft = points[i]\n",
    "            for i in points[:]:\n",
    "                if minleft[1] >= i[0]:\n",
    "                    points.remove(i)\n",
    "            return self.findMinArrowShots(points) + 1\n",
    "'''    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinArrowShots(self, points: list) -> int:\n",
    "        points.sort()\n",
    "        n = len(points)\n",
    "        if not n:\n",
    "            return 0\n",
    "        return self.handle(points, n)\n",
    "\n",
    "    def handle(self, balls: list, n, count=0):\n",
    "        ball = balls[0]\n",
    "        if n == 1:\n",
    "            return count + 1\n",
    "        neighbor = balls[1]\n",
    "        if neighbor[0] > ball[1]:\n",
    "            balls.pop(0)\n",
    "            count += 1\n",
    "            return self.handle(balls, n - 1, count)\n",
    "        # totally in this ball\n",
    "        if neighbor[1] <= ball[1]:\n",
    "            balls.pop(0)  # just remove the outer ball\n",
    "            return self.handle(balls, n - 1, count)\n",
    "        # intersect\n",
    "        balls.pop(0)\n",
    "        balls[0] = [neighbor[0], ball[1]]  # merge the first two balls\n",
    "        return self.handle(balls, n - 1, count)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def my_sort(self, list, begin, end):\n",
    "        i, j = begin, end\n",
    "        if i>=j:\n",
    "            return list\n",
    "        aim = list[begin]\n",
    "        while i<j:\n",
    "            while i<j and list[j][1]>=aim[1]:\n",
    "                j -= 1\n",
    "            if i<j:\n",
    "                list[i] = list[j]\n",
    "                i+=1\n",
    "            while i<j and list[i][1]<= aim[1]:\n",
    "                i += 1\n",
    "            if i<j:\n",
    "                list[j] = list[i]\n",
    "                j -= 1\n",
    "        list[j] = aim\n",
    "        self.my_sort(list, begin, j-1)\n",
    "        self.my_sort(list, j+1, end)\n",
    "        return list\n",
    "\n",
    "\n",
    "    def findMinArrowShots(self, points: List[List[int]]) -> int:\n",
    "        if  len(points) == 0:\n",
    "            return 0\n",
    "\n",
    "        points = self.my_sort(points, 0, len(points)-1)\n",
    "        result = [points[0]]\n",
    "        i = 0\n",
    "        while i < len(points):\n",
    "            idx = 1\n",
    "            while i + idx < len(points) and points[i][1] >= points[i+idx][0]:\n",
    "                idx += 1\n",
    "            i = i + idx\n",
    "            if i < len(points):\n",
    "                result.append(points[i])\n",
    "\n",
    "        return len(result)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinArrowShots(self, points: List[List[int]]) -> int:\n",
    "\n",
    "        points=sorted(points,key=lambda x:x[0])\n",
    "        self.ans=0\n",
    "        def get(i=0):\n",
    "\n",
    "            if i>=len(points):\n",
    "                return\n",
    "\n",
    "            sx,sy=points[i]\n",
    "\n",
    "            \n",
    "\n",
    "            while i<len(points):\n",
    "                if i+1<len(points):\n",
    "                    s2x,s2y=points[i+1]\n",
    "                    i+=1\n",
    "                    if sy>=s2x:\n",
    "                        sx=s2x\n",
    "                        if s2y<=sy:\n",
    "                            sy=s2y\n",
    "                        \n",
    "                    else:\n",
    "                        self.ans+=1\n",
    "                        break\n",
    "                else:\n",
    "                    self.ans+=1\n",
    "                    return\n",
    "            \n",
    "            get(i)\n",
    "        get()\n",
    "        return self.ans    \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinArrowShots(self, points: List[List[int]]) -> int:\n",
    "        ballons = sorted(points, key=lambda x: x[1])\n",
    "        ballonShotedMarks = [False] * len(ballons)\n",
    "#         print(ballons)\n",
    "        def findMinArrowShots(leftMostBallonIndex=0):\n",
    "            if all(ballonShotedMarks) is True: return 0\n",
    "#             print(leftMostBallonIndex)\n",
    "            ballonShotedMarks[leftMostBallonIndex] = True\n",
    "            shotPos = ballons[leftMostBallonIndex][1]\n",
    "            \n",
    "            leftMostBallonIndexOrigin = leftMostBallonIndex \n",
    "            for i in range(leftMostBallonIndexOrigin+1, len(ballons)):\n",
    "                if ballonShotedMarks[i]:\n",
    "                    continue\n",
    "                if ballons[i][0] <= shotPos:\n",
    "                    ballonShotedMarks[i] = True\n",
    "                elif leftMostBallonIndex == leftMostBallonIndexOrigin:\n",
    "                    leftMostBallonIndex = i\n",
    "            return 1+findMinArrowShots(leftMostBallonIndex)\n",
    "        return findMinArrowShots()\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinArrowShots(self, points: List[List[int]]) -> int:\n",
    "        if points == [] :\n",
    "            return 0\n",
    "        a = sorted(points,key = lambda x : x[1])\n",
    "        print(a)\n",
    "        res = len(a)\n",
    "        if res == 1  :\n",
    "            return res \n",
    "        b = a[0][1]\n",
    "        for i in range(1,len(a)) :\n",
    "            if a[i][0] <= b :\n",
    "                res -= 1 \n",
    "            else :\n",
    "                b = a[i][1]\n",
    "      \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinArrowShots(self, points: List[List[int]]) -> int:\n",
    "\n",
    "        n = 1\n",
    "        points.sort()\n",
    "\n",
    "        for i in reversed(range(len(points)-1)):\n",
    "\n",
    "            if ((points[i][1]>=points[i+1][0]) & (points[i][0]<=points[i+1][0])):\n",
    "                points.pop(i)\n",
    "            else: n+=1\n",
    "        return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def findMinArrowShots(self, points: List[List[int]]) -> int:\n",
    "        if len(points) == 0:\n",
    "            return 0\n",
    "        arr = np.array(points)\n",
    "        arr = arr[np.lexsort(arr.T)]\n",
    "        counts = 1\n",
    "        i = 0\n",
    "        j = 1\n",
    "        while j < len(points):\n",
    "            if arr[i][1] >= arr[j][0]:\n",
    "                j += 1\n",
    "            else:\n",
    "                i = j\n",
    "                counts += 1\n",
    "                j = i+1\n",
    "        return counts"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinArrowShots(self, points: List[List[int]]) -> int:\n",
    "        points.sort(key=operator.itemgetter(1),reverse=True)\n",
    "        res = []\n",
    "        while len(points)!=0:\n",
    "            now = points.pop()\n",
    "            res.append(now)\n",
    "            i = len(points) - 1\n",
    "            while i>=0:\n",
    "                if now[1]>=points[i][0]:\n",
    "                    points.pop(i)\n",
    "                    i-=1\n",
    "                else:\n",
    "                    break\n",
    "\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinArrowShots(self, points: List[List[int]]) -> int:\n",
    "        points.sort()\n",
    "        ans = 1\n",
    "        pre = points.pop()\n",
    "        while points:\n",
    "            cur = points.pop()\n",
    "            if cur[1] >= pre[0]:\n",
    "                pre = [pre[0], min(cur[1], pre[1])]\n",
    "            else:\n",
    "                pre = cur\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinArrowShots(self, points: List[List[int]]) -> int:\n",
    "        points.sort()\n",
    "        res=1\n",
    "        for i in range(1,len(points)):\n",
    "            if points[i-1][1]<points[i][0]:\n",
    "                res+=1\n",
    "            if points[i-1][1]>=points[i][0] and points[i-1][1]<points[i][1]:\n",
    "                points[i]=points[i-1]\n",
    "\n",
    "        return res\n",
    " \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "class Solution:\n",
    "    def findMinArrowShots(self, points: List[List[int]]) -> int:\n",
    "        # print(points)\n",
    "        if len(points) == 0:\n",
    "            return 0\n",
    "        #对气球按照左端点排序\n",
    "        points = sorted(points, key=lambda student: student[0])\n",
    "        shoot_num = 1\n",
    "        shoot_begin = points[0][0]\n",
    "        shoot_end = points[0][1]\n",
    "        for i in range(1,len(points)):\n",
    "            if points[i][0] <= shoot_end:\n",
    "                shoot_begin = points[i][0]\n",
    "                if shoot_end > points[i][1]:\n",
    "                    shoot_end = points[i][1]\n",
    "            else:\n",
    "                shoot_num+=1\n",
    "                shoot_begin = points[i][0]\n",
    "                shoot_end = points[i][1]\n",
    "        return shoot_num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinArrowShots(self, points: List[List[int]]) -> int:\n",
    "        points.sort(key=lambda x:x[1])\n",
    "        ans = 0\n",
    "        j = 0\n",
    "        while j < len(points) and points[j]:\n",
    "            ans += 1\n",
    "            i = j+1\n",
    "            while i<len(points) and points[i][0] <= points[j][1]:\n",
    "                points[i] = []\n",
    "                i += 1    \n",
    "            j = i\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def findMinArrowShots(self, points: List[List[int]]) -> int:\r\n",
    "        points.sort(key=lambda x: x[1])\r\n",
    "        cnt = 1\r\n",
    "        for i in range(1, len(points)):\r\n",
    "            if points[i][0] <= points[i-1][1]:\r\n",
    "                points[i] = [max(points[i-1][0], points[i][0]), points[i-1][1]]\r\n",
    "            else:\r\n",
    "                cnt += 1\r\n",
    "        return cnt\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinArrowShots(self, points: List[List[int]]) -> int:\n",
    "        points.sort()\n",
    "        print(points)\n",
    "        l = len(points)\n",
    "        i,res=0,0\n",
    "        while i < l-1:\n",
    "            if points[i][1]<points[i+1][0]:\n",
    "                i+=1\n",
    "                print(\"1\")\n",
    "            elif points[i][1]<=points[i+1][1]:\n",
    "                points[i+1]=points[i]\n",
    "                i+=1\n",
    "                res+=1\n",
    "                print(\"2\")\n",
    "                print(\"i:\",i)\n",
    "            else:\n",
    "                i+=1\n",
    "                res+=1\n",
    "                print(\"3\")\n",
    "                print(\"i:\",i)\n",
    "        return l-res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinArrowShots(self, points: List[List[int]]) -> int:\n",
    "        # 按 start 排\n",
    "        spoints = points\n",
    "        spoints.sort()\n",
    "        ends_dict = {}\n",
    "\n",
    "\n",
    "        for start, end in spoints:\n",
    "            if end in ends_dict.keys():\n",
    "                ends_dict[end] += 1\n",
    "            else:\n",
    "                ends_dict[end] = 1\n",
    "\n",
    "        ends = sorted(ends_dict)\n",
    "        spoints.reverse()\n",
    "        res = 0\n",
    "        \n",
    "        for pop_end   in  ends:\n",
    "            # 从最左边的end开始射\n",
    "            # print('先射出一箭 end = ', pop_end)\n",
    "            # 先爆掉一个汽球\n",
    "            if ends_dict[pop_end] <= 0:\n",
    "                continue\n",
    "        \n",
    "            res += 1\n",
    "\n",
    "            # 把穿过的弹出，其 start < end\n",
    "            # 箭穿过的气球 其end必然比 pop_end 大，所以只要看start < end 就行 （想想为什么）\n",
    "            while spoints:\n",
    "                if spoints[-1][0] <= pop_end:\n",
    "                    # 爆掉一个汽球， ends 里面减掉对应的一个, spoints 里面也减掉\n",
    "                    ppoint = spoints.pop()\n",
    "                    ends_dict[ppoint[1]] -= 1\n",
    "                else:\n",
    "                    break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinArrowShots(self, points: List[List[int]]) -> int:\n",
    "        points.sort(key=lambda x: x[1])\n",
    "        ans = 0\n",
    "        for i in range(0, len(points) - 1):\n",
    "            if points[i][1] >= points[i+1][0]:\n",
    "                ans -= 1\n",
    "\n",
    "                points[i + 1][1] = points[i][1]\n",
    "                points[i + 1][0] = max(points[i + 1][0], points[i][0])\n",
    "\n",
    "\n",
    "        return ans + len(points)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinArrowShots(self, points: List[List[int]]) -> int:\n",
    "        points.sort()\n",
    "        res = 1\n",
    "\n",
    "        for i in range(1, len(points)):\n",
    "            if points[i][0] > points[i-1][1]:\n",
    "                res += 1\n",
    "            else:\n",
    "                points[i][1] = min(points[i-1][1], points[i][1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinArrowShots(self, points: List[List[int]]) -> int:\n",
    "        points.sort(reverse = True)\n",
    "        shotX = points[0][1]\n",
    "        shots = 1\n",
    "        while points:\n",
    "            target = points.pop()\n",
    "            if shotX > target[1]:\n",
    "                shotX = target[1]\n",
    "            if shotX < target[0]:\n",
    "                shots += 1\n",
    "                shotX = target[1]\n",
    "        return shots"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinArrowShots(self, points: List[List[int]]) -> int:\n",
    "        shot = 0\n",
    "        points.sort()\n",
    "        while points:\n",
    "            arrow = points[-1][0]\n",
    "            shot = shot + 1\n",
    "            i = len(points) - 1\n",
    "            while i >= 0:\n",
    "                if arrow > points[i][1]:\n",
    "                    break\n",
    "                else:\n",
    "                    points.pop()\n",
    "                i = i - 1\n",
    "        \n",
    "        return shot"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinArrowShots(self, points: List[List[int]]) -> int:\n",
    "        points.sort()\n",
    "        arrow = points.pop()\n",
    "        ans = 0\n",
    "        while points:\n",
    "            left, right = points.pop()\n",
    "            if left<=arrow[1] and right>=arrow[0]:\n",
    "                arrow[0] = max(arrow[0], left)\n",
    "                arrow[1] = min(arrow[1], right)\n",
    "            else:\n",
    "                ans += 1\n",
    "                arrow = [left, right]\n",
    "        return ans + 1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinArrowShots(self, points: List[List[int]]) -> int:\n",
    "        shot = 0\n",
    "        if not points:\n",
    "            return shot\n",
    "        points.sort(key = lambda x:x[1])\n",
    "        for i in range(len(points)):\n",
    "            if points[i][0] <= points[i-1][1]:\n",
    "                shot += 1\n",
    "                if points[i][1] > points[i-1][1]:\n",
    "                    points[i] = points[i-1]\n",
    "        return len(points) - shot + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinArrowShots(self, points: List[List[int]]) -> int:\n",
    "        if len(points) == 0: return 0\n",
    "        points.sort(key=lambda x: x[0])\n",
    "        result = 1\n",
    "        temp=points[0][1]\n",
    "        \n",
    "        for i in range(1, len(points)):\n",
    "            if points[i][0] > temp: # 气球i和气球i-1不挨着，注意这里不是>=\n",
    "                result += 1    \n",
    "                temp=points[i][1]\n",
    "            else:\n",
    "                temp = min(temp, points[i][1]) # 更新重叠气球最小右边界\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinArrowShots(self, points: List[List[int]]) -> int:\n",
    "        points.sort(key=lambda x:(x[1],x[0]), reverse=True)\n",
    "        a = 0\n",
    "        limit = points[-1][1]\n",
    "        while len(points) > 0:\n",
    "            if points[-1][0] <= limit:\n",
    "                points.pop()\n",
    "                if len(points) == 0:\n",
    "                    a+=1\n",
    "            else:\n",
    "                limit = points[-1][1]\n",
    "                a += 1\n",
    "\n",
    " \n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinArrowShots(self, points: List[List[int]]) -> int:\n",
    "        if len(points) == 1:\n",
    "            return 1\n",
    "        points.sort(key=lambda x: x[0])\n",
    "        print(points)\n",
    "        mst, med = points[0]\n",
    "        result = 1\n",
    "        for point in points[1:]:\n",
    "            st, ed = point\n",
    "            mst = max(st, mst)\n",
    "            med = min(ed, med)\n",
    "            if mst <= med:\n",
    "                continue\n",
    "            else:\n",
    "                mst, med = st, ed\n",
    "                result+=1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinArrowShots(self, points: List[List[int]]) -> int:\n",
    "        points.sort(key=lambda x: (x[0], x[1]))\n",
    "        print(points)\n",
    "        res = 1\n",
    "        for i in range(1, len(points)):\n",
    "            if points[i][0] > points[i - 1][1]:\n",
    "                res += 1\n",
    "            else:\n",
    "                points[i][1] = min(points[i - 1][1], points[i][1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinArrowShots(self, points: List[List[int]]) -> int:\n",
    "        points.sort(key = lambda i:(i[0],i[1]))\n",
    "        res = 0\n",
    "        pre = points[0]\n",
    "        print(points)\n",
    "        for i in range(1, len(points)):\n",
    "            if points[i][0] <= pre[1]:\n",
    "                pre = [points[i][0], min(pre[1], points[i][1])]\n",
    "            else:\n",
    "                print(pre)\n",
    "                res += 1\n",
    "                pre = points[i]\n",
    "        return res + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinArrowShots(self, points: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        n = len(points)\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        points.sort(reverse=True)\n",
    "        # points.append([0,0])  #增加结尾\n",
    "        \n",
    "        for i in range(n-1):\n",
    "            if points[i][0] <= points[i+1][1]:\n",
    "                points[i+1][0] = max(points[i][0], points[i+1][0])\n",
    "                points[i+1][1] = min(points[i][1], points[i+1][1])\n",
    "            else:\n",
    "                res += 1\n",
    "        return res+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinArrowShots(self, points: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        n = len(points)\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        points.sort(reverse=True)\n",
    "        # points.append([0,0])  #增加结尾\n",
    "        \n",
    "        for i in range(n-1):\n",
    "            if points[i][0] <= points[i+1][1]:\n",
    "                points[i+1][0] = max(points[i][0], points[i+1][0])\n",
    "                points[i+1][1] = min(points[i][1], points[i+1][1])\n",
    "            else:\n",
    "                res += 1\n",
    "        return res+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinArrowShots(self, points: List[List[int]]) -> int:\n",
    "        if len(points) == 0: return 0\n",
    "        points.sort(key=lambda x: x[0])\n",
    "        result = 1\n",
    "        for i in range(1, len(points)):\n",
    "            if points[i][0] > points[i - 1][1]: # 气球i和气球i-1不挨着，注意这里不是>=\n",
    "                result += 1     \n",
    "            else:\n",
    "                points[i][1] = min(points[i - 1][1], points[i][1]) # 更新重叠气球最小右边界\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinArrowShots(self, points: List[List[int]]) -> int:\n",
    "        points.sort(key=lambda x: x[0])\n",
    "        result = 1\n",
    "        for i in range(1, len(points)):\n",
    "            if points[i][0] > points[i - 1][1]:\n",
    "                result += 1\n",
    "            else:\n",
    "                points[i][1] = min(points[i - 1][1], points[i][1])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinArrowShots(self, points: List[List[int]]) -> int:\n",
    "        points.sort(key=lambda x:x[0])\n",
    "        if len(points) == 0:\n",
    "            return 0\n",
    "        res = 1\n",
    "        for i in range(1,len(points)):\n",
    "            if points[i][0] > points[i-1][1]:\n",
    "                res = res + 1\n",
    "            else:\n",
    "                points[i][1] = min(points[i-1][1],points[i][1])\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinArrowShots(self, points: List[List[int]]) -> int:\n",
    "        # 可以看作区间合并,与视频剪辑那道题类似,但那个取并集,这个取交集\n",
    "        points.sort()\n",
    "        tmp = deque(points)\n",
    "        \n",
    "        print(tmp)\n",
    "        n = len(points)\n",
    "        idx = 0\n",
    "        count = 0\n",
    "        while (count<n-1) :\n",
    "            count += 1\n",
    "            if tmp[idx][1]>=tmp[idx+1][0]:\n",
    "                tmp[idx+1][1] = min(tmp[idx+1][1],tmp[idx][1])\n",
    "                tmp.popleft()\n",
    "            else:\n",
    "                idx += 1\n",
    "        return len(tmp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMinArrowShots(self, points: List[List[int]]) -> int:\n",
    "        if not points:\n",
    "            return 0\n",
    "        points.sort(key= lambda x:x[1])\n",
    "        count = 1\n",
    "        x_end = points[0][1]\n",
    "        for i in points:\n",
    "            start = i[0]\n",
    "            if start > x_end:\n",
    "                count += 1\n",
    "                x_end = i[1]\n",
    "        return count\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
